package myself.a004QuickSor;

import myself.a000util.Logarithm;

/**
 * @author 叶之越
 * Description
 * Date 2021/1/23
 * Time 11:11
 * Mail 739153436@qq.com
 */
public class QuickSort {
    public static void main(String[] args) {
        Logarithm.QuickSort.check(QuickSort.class, "quickSort1");
        Logarithm.QuickSort.check(QuickSort.class, "quickSort2");
        Logarithm.QuickSort.check(QuickSort.class, "quickSort3");
    }

    // 版本一：每次只能排序出一个数
    public void quickSort1(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int mid = DutchFlag.partition(arr, L, R);
        quickSort1(arr, L, mid - 1);
        quickSort1(arr, mid + 1, R);
    }

    // 版本二：一次能够排序出1个或者以上的数
    public void quickSort2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] mid = DutchFlag.netherlandsFlag(arr, L, R);
        quickSort2(arr, L, mid[0] - 1);
        quickSort2(arr, mid[1] + 1, R);
    }

    // 版本三：对于版本二的优化，随机获取最右边的标志，运气好会得到更好的性能
    public void quickSort3(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        // 随机将一个数和右边的数替换作为标准值
        DutchFlag.swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] mid = DutchFlag.netherlandsFlag(arr, L, R);
        quickSort3(arr, L, mid[0] - 1);
        quickSort3(arr, mid[1] + 1, R);
    }
}
